package com.lbt.javaSE.jianzhioffer;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class JZ4TreeNode {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    public static Queue<TreeNode> queue;

    public static void main(String[] args) {
      JZ4TreeNode jz4TreeNode=new JZ4TreeNode();
     int [] pre=new int[]{1,2,4,7,3,5,6,8};
     int [] in=new int []{4,7,2,1,5,3,8,6};
     TreeNode treeNode = jz4TreeNode.reConstructBinaryTree(pre, in);
     jz4TreeNode.showTree(treeNode);
//     System.out.println(queue.size());

    }
    //递归实现
    //例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
           if(pre.length==0||in.length==0){
            return null;
           }
           TreeNode root= new TreeNode(pre[0]);
           for(int i=0;i<in.length;i++) {
            if (in[i] == pre[0]) {
             // 左子树，注意 copyOfRange 函数，左闭右开
             root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
             // 右子树，注意 copyOfRange 函数，左闭右开
             root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
            }
           }
           return root;
    }
    //前序遍历 跟左右
   public void showTree(TreeNode head){
         if(head==null){
          return;
         }else {
          queue=new LinkedList<>();
          queue.offer(head);
          System.out.println(head.val);
          if(head.left!=null){
           TreeNode left=head.left;
           showTree(left);
          }
          if(head.right!=null){
           TreeNode right=head.right;
           showTree(right);
          }
         }

    }
}
